package com.yusong.algorithm.link;

public class Link92 {

    public static void main(String[] args) {
        int[] data = {3,5};
        ListNode node = ListNodeUtil.create(data);

        Link92 demo = new Link92();
        node = demo.reverseBetween(node, 1, 2);
        ListNodeUtil.printNode(node);
    }


    public ListNode reverseBetween(ListNode head, int m, int n) {
        timesMax = (n+1 -m)/2;
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        recurseChange(dummyHead,dummyHead, m, n);
        return dummyHead.next;
    }
    //全局变量正向遍历
    ListNode leftStart;
    int timesMax;
    int exchangeTimes = 0;

    //回溯搞定逆向遍历
    public void recurseChange(ListNode left, ListNode right, int m, int n){
        //中止条件
        if(n == 0){
            return;
        }
        if(m > 0){
            left = left.next;
            leftStart = left;
            m--;
        }
        if(n > 0){
            right = right.next;
            n--;
        }
        recurseChange(left, right, m, n);
        //交换正向遍历和逆向遍历的数据
        if(exchangeTimes < timesMax){
            int valTmp = right.val;
            right.val = leftStart.val;
            leftStart.val = valTmp;
            leftStart = leftStart.next;
            exchangeTimes++;
        }

    }
}
